﻿#pragma once
#include "Index.h"

/**
 * 最后K个数的乘积.
 * https://leetcode.cn/problems/product-of-the-last-k-numbers/
 * 前缀和 设计 队列 数组 数学 数据流
 *
 * 请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
 * 1. add(int num)
 * 将数字 num 添加到当前数字列表的最后面。
 *
 * 2. getProduct(int k)
 * 返回当前数字列表中，最后 k 个数字的乘积。
 * 你可以假设当前列表中始终 至少 包含 k 个数字。
 * 题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
 */
class ProductOfNumbers
{
public:
    ProductOfNumbers() : lastZeroIndex(0)
    {
        preMulti.push_back(0);
    }

    void add(int num)
    {
        if (num == 0)
        {
            lastZeroIndex = preMulti.size();
            preMulti.push_back(0);
        }
        else if (preMulti.back() == 0)
            preMulti.push_back(num);
        else
            preMulti.push_back(preMulti.back() * num);
    }

    int getProduct(int lastK)
    {
        //不够k个数
        if (preMulti.size() - 1 < lastK)
            return 0;

        const int lastIndex = preMulti.size() - lastK;
        DEV_ASSERT_BREAK(lastIndex >= 1);
        //从lastIndex开始之后至少有一个0，乘积的结果为0
        if (lastIndex <= lastZeroIndex)
            return 0;
        //lastIndex之前的一个数为0，后面的数都不为0，直接返回lastIndex到最后数字的乘积
        if (preMulti[lastIndex - 1] == 0)
            return preMulti.back();

        return preMulti.back() / preMulti[lastIndex - 1];
    }
private:
    std::vector<int> preMulti;
    int lastZeroIndex;
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(ProductOfNumbersTest, getProduct)
{
    TEST_SOLUTION1(ProductOfNumbers, ProductOfNumbers, &)
    {
        __slnTestor.setTestTimes(100);

        std::vector<int> nums;
        constexpr int numsSize = 100;
        constexpr int numMaxVal = 3;
        constexpr int numMinVal = -3;

        for (int i = 0; i < numsSize; ++i)
        {
            const int addNum = TestingUtil::randIntBetween(numMinVal, numMaxVal);
            nums.push_back(addNum);
            solution->add(addNum);

            if (TestingUtil::randBoolean("getProduct"))
            {
                for (int k = 1; k <= nums.size(); ++k)
                {
                    const auto resultProduct = solution->getProduct(k);

                    int expectProduct = 1;
                    auto rit = nums.rbegin();
                    for (int j = 1; j <= k; ++j, ++rit)
                        expectProduct *= *rit;

                    ASSERT_EQ(resultProduct, expectProduct);

                    if (nums[nums.size() - k] == 0)
                        break;
                }
            }
        }
    };
}
#endif